#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class Heap:
    def min_lessor(a, b):
        return a < b

    def max_lessor(a, b):
        return a > b

    def build_min(self, nums, lessor=min_lessor):
        # return self.build(nums, Heap.min_lessor)
        return self.build(nums, lessor)

    def build_max(self, nums, lessor=max_lessor):
        return self.build(nums, lessor)

    def build(self, nums, lessor):
        # 通用build: 顶部放置最小元素
        start = (len(nums) - 2) // 2
        end = 0

        # print(start, end)
        for idx in range(start, end-1, -1):
            self.adjust(nums, idx, lessor)

        return nums

    def adjust_min(self, nums, idx, lessor=min_lessor):
        # self.adjust(nums, idx, Heap.min_lessor)
        self.adjust(nums, idx, lessor)

    def adjust_max(self, nums, idx, lessor):
        pass

    def adjust(self, nums, idx, lessor):
        # print("adjust", idx)
        if idx > (len(nums) - 2) // 2:
            return

        cur = nums[idx]
        left_idx  = idx * 2 + 1
        right_idx = idx * 2 + 2

        assert left_idx < len(nums)

        bottom_min_idx = 0
        if right_idx >= len(nums):
            # print("right_idx greator", idx, len(nums))
            bottom_min_idx = left_idx
        else:
            if lessor(nums[left_idx], nums[right_idx]):
                bottom_min_idx = left_idx
            else:
                bottom_min_idx = right_idx

        if lessor(nums[bottom_min_idx], nums[idx]):
            nums[idx], nums[bottom_min_idx] = nums[bottom_min_idx], nums[idx]
            self.adjust(nums, bottom_min_idx, lessor)



def pop_heap(nums, call_back):
    if len(nums) == 0:
        return None, False

    top = nums[0]
    will_continue = call_back(top, nums)

    return top, will_continue



class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        return merging_sort_k(lists)


def merging_sort_k(k_way_inputs):
    if len(k_way_inputs) == 0:
        return None

    heap_nums = []

    for head in k_way_inputs:
        if head is not None:
            heap_nums.append(head)

    # if len(heap_nums) == 0:
    #     return None

    if len(heap_nums) == 1:
        # 只有1路
        return  heap_nums[0]


    lessor=lambda a,b : a.val < b.val
    h = Heap()
    h.build_min(heap_nums, lessor=lessor)


    # ------------------- result  ---------------------
    dummy_head = ListNode(-1)
    tail = dummy_head

    def push_pop_idx_in_k(node, nums):
        nonlocal tail
        tail.next, tail = node, node

        print("process node", node.val)

        if node.next is None:
            # 其中1路结束了
            nums[0] = nums[-1]
            nums.pop()

            if len(nums) == 0:
                # 只剩0路了(所有数据都处理完毕了)
                return False
        else:
            nums[0] = node.next

        h.adjust_min(nums, 0, lessor=lessor)
        return True



    top, will_continue = pop_heap(heap_nums, push_pop_idx_in_k)
    while top is not None and will_continue:
        top, will_continue = pop_heap(heap_nums, push_pop_idx_in_k)

    # assert top is not None

    return dummy_head.next


# ------------------- test  ---------------------


class ListNode(object):
    def __init__(self, x, next=None):
        self.val = x
        self.next = next


def test_merging_sort_k():
    l12 = ListNode(7, None)
    l11 = ListNode(5, l12)
    l10 = ListNode(1, l11)

    l22 = ListNode(5, None)
    l21 = ListNode(3, l22)
    l20 = ListNode(2, l21)

    inputs = [
        l10,
        l20,
    ]

    # result = merging_sort_k(inputs)
    result = Solution().mergeKLists(inputs)
    print("[merging sort result]", result.val)
    print("[merging sort result]", result.next.val)

    # print(len(result))


def main():
    print("start main")
    test_merging_sort_k()

if __name__ == "__main__":
    main()

def test():
    s = Solution()

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
